//1.前缀和 - 连续数组
//技巧: 将0改为-1, 1还是1, 然后求和为0的最长数组的长度 - 前缀和 + 哈希表
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        for(auto& x : nums) 
            if(x == 0) x = -1;
        unordered_map<int, int> hash; //前缀和-第一次出现前缀和的下标
        hash[0] = -1;
        int sum = 0, ret = 0;
        for(int i = 0; i < n; i++)
        {
            sum += nums[i];
            if(hash.count(sum)) ret = max(ret, i - hash[sum]);
            else hash[sum] = i;
        }
        return ret;
    }
};


//2.前缀和 - 矩阵区域和
//注意下标的映射关系
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int n = mat.size(), m = mat[0].size();
        //1.预处理前缀和
        int sum[110][110] = {0};
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                sum[i][j] = sum[i-1][j] + sum[i][j-1] + mat[i - 1][j - 1] - sum[i-1][j-1];

        //2.使用前缀和矩阵
        vector<vector<int>> ret(n, vector<int>(m));
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                int x1 = max(i - k, 0) + 1, x2 = min(i + k, n - 1) + 1;
                int y1 = max(j - k, 0) + 1, y2 = min(j + k, m - 1) + 1;
                ret[i][j] = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1- 1];
            }
        }
        return ret;
    }
};
